<!DOCTYPE HTML>
<html lang="ch" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>实验3：内存管理 - nudt os lab book (2023)</title>


        <!-- Custom HTML head -->
        
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="favicon.svg">
        <link rel="shortcut icon" href="favicon.png">
        <link rel="stylesheet" href="css/variables.css">
        <link rel="stylesheet" href="css/general.css">
        <link rel="stylesheet" href="css/chrome.css">
        <link rel="stylesheet" href="css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="highlight.css">
        <link rel="stylesheet" href="tomorrow-night.css">
        <link rel="stylesheet" href="ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
    <div id="body-container">
        <!-- Provide site root to javascript -->
        <script>
            var path_to_root = "";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script>
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script>
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script>
            var html = document.querySelector('html');
            var sidebar = null;
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            } else {
                sidebar = 'hidden';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded affix "><li class="part-title">操作系统实验指南</li><li class="chapter-item expanded "><a href="lab_0.html"><strong aria-hidden="true">1.</strong> 准备：实验环境搭建</a></li><li class="chapter-item expanded "><a href="lab_1.html"><strong aria-hidden="true">2.</strong> 实验1：向Framebuffer中打印字符</a></li><li class="chapter-item expanded "><a href="lab_2.html"><strong aria-hidden="true">3.</strong> 实验2：异常处理和硬件中断</a></li><li class="chapter-item expanded "><a href="lab_3.html" class="active"><strong aria-hidden="true">4.</strong> 实验3：内存管理</a></li><li class="chapter-item expanded "><a href="lab_4.html"><strong aria-hidden="true">5.</strong> 实验4：协程与异步</a></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">nudt os lab book (2023)</h1>

                    <div class="right-buttons">
                        <a href="print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script>
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="实验3内存管理"><a class="header" href="#实验3内存管理">实验3：内存管理</a></h1>
<h2 id="实验导读"><a class="header" href="#实验导读">实验导读</a></h2>
<p>大家已经完成了串口中断和鼠标中断的处理，本次实验需要在系统增加内存管理相关功能，从而支持操作系统让不同应用程序在同时运行时可以安全的共同使用物理内存资源。</p>
<p>本实验提供一份基础代码，还有部分需要实验者自己补充，已在代码中用“TODO”标出。</p>
<ul>
<li><a href="#%E5%BC%95%E5%AF%BC%E5%8A%A0%E8%BD%BD%E7%A8%8B%E5%BA%8F%E7%9A%84%E9%85%8D%E7%BD%AE">引导加载程序的配置</a></li>
<li><a href="#%E7%89%A9%E7%90%86%E9%A1%B5%E5%B8%A7%E5%88%86%E9%85%8D%E5%99%A8">物理页帧分配器</a></li>
<li><a href="#%E7%89%A9%E7%90%86%E9%A1%B5%E5%B8%A7%E5%88%B0%E8%99%9A%E6%8B%9F%E9%A1%B5%E7%9A%84%E6%98%A0%E5%B0%84">物理页帧到虚拟页的映射</a></li>
<li><a href="#%E5%AE%9E%E7%8E%B0%E5%A0%86%E5%86%85%E5%AD%98%E5%88%86%E9%85%8D%E5%99%A8%E9%80%89%E5%81%9A">实现堆内存分配器（*选做）</a></li>
<li><a href="#%E5%91%BD%E4%BB%A4%E8%A7%A3%E9%87%8A%E5%99%A8%E7%9A%84%E9%87%8D%E6%96%B0%E5%AE%9E%E7%8E%B0%E9%80%89%E5%81%9A">命令解释器的重新实现（*选做）</a></li>
<li><a href="#%E5%B0%8F%E7%BB%93">小结</a></li>
<li><a href="#%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%AE%9E%E9%AA%8C">下一个实验</a></li>
<li><a href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99">参考资料</a></li>
</ul>
<h3 id="引导加载程序的配置"><a class="header" href="#引导加载程序的配置">引导加载程序的配置</a></h3>
<p>大家在实验1中已经了解了内核在加载之后从低地址转移到高地址的过程，这样将内核数据加载到高地址的主要原因是希望在后续内核功能丰富之后仍然有较大的生长空间。但是，当我们需要实现内存管理中访问页表的操作时，由于内核已经加载到了虚拟地址，因此需要额外的支持来实现从内核访问页表的过程。</p>
<p>引导加载程序创建了内核运行的页表，有权访问页表，因此也可以创建我们需要的任何映射，我们可以通过配置bootloader，将整个物理内存映射到虚拟地址空间中的某个位置。因此，内核可以访问所有物理内存，并且可以遵循 “映射完整物理内存” 方法。配置方式如下所示：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 在kernel/main.rs中
use bootloader_api::{config::Mapping, BootloaderConfig};

/// 物理地址偏移
pub const KERNEL_PHY_OFFSET: usize = 0xFFFF_FF80_0000_0000;

/// bootloader配置
pub static BOOTLOADER_CONFIG: BootloaderConfig = {
    let mut config = BootloaderConfig::new_default();
    config.mappings.physical_memory = Some(Mapping::FixedAddress(KERNEL_PHY_OFFSET as _));
    config
};

// 使用bootloader_api库提供的宏声明内核入口，传入config配置信息
bootloader_api::entry_point!(kernel_main, config = &amp;BOOTLOADER_CONFIG);
<span class="boring">}</span></code></pre></pre>
<p>引导加载程序之后会传递一个<code>引导信息BootInfo</code>结构给内核，从而传达虚拟地址范围。</p>
<h3 id="物理页帧分配器"><a class="header" href="#物理页帧分配器">物理页帧分配器</a></h3>
<p>现在我们可以访问物理内存了，首先来实现一个物理页帧分配器。新建一个内存管理模块，利用<code>bootinfo</code>的信息对其进行初始化：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 在kernel/lib.rs中
mod mem;

/// 各类初始化函数
pub fn init&lt;'a&gt;(boot_info: &amp;'a mut bootloader_api::BootInfo) {
    [...]
    // 初始化内存管理
    mem::init(&amp;mut boot_info.memory_regions);
}
<span class="boring">}</span></code></pre></pre>
<p>接下来引入物理页帧模块：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 在kernel/src/mem/mod.rs中
mod frame_allocator;
<span class="boring">}</span></code></pre></pre>
<p>在<code>kernel/src/mem/frame_allocator.rs</code>中，对物理页帧进行初始化。通过从<code>bootloader</code>传递来的<code>info</code>，我们可以获得虚拟地址的范围<code>memory_regions</code>：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use bootloader_api::info::MemoryRegions;

/// 初始化页帧分配器
pub fn init_frame_allocator&lt;'a&gt;(memory_regions: &amp;'a mut MemoryRegions) {
    serial_println!(&quot;[Kernel] Memory regions:&quot;);
    for region in memory_regions.into_iter() {
        serial_println!(&quot;    {:x?}&quot;, region);
    }
    [...]
}
<span class="boring">}</span></code></pre></pre>
<p>打印出的结果如下所示：
<img src="lab3_memory_region.png" alt="pic" /></p>
<p>在上图中，有标记为<code>Usable</code>的区域为可用内存，大家可以参考blog_os中<a href="https://www.bookstack.cn/read/writing-an-os-in-rust/09-paging-implementation.md">分页实现</a>中的方法将内存映射转换为可用帧的迭代器。</p>
<p>接下来，我们需要设计页帧分配器结构体，并创建全局变量，在<code>init_frame_allocator</code>函数中初始化全局变量，并在<code>allocate_frame</code>、<code>allocate_frame_cont</code>、<code>deallocate_frame</code>函数中使用全局变量完成相关操作,补全以下代码中的TODO部分。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>/// 初始化页帧分配器
pub fn init_frame_allocator&lt;'a&gt;(memory_regions: &amp;'a mut MemoryRegions) {
    [...]
    // TODO
}

/// 申请一个可用页帧，返回首地址
pub fn allocate_frame() -&gt; Option&lt;usize&gt; {
    // TODO
    None
}

/// 申请一组连续的页帧，返回第一个页帧的首地址
pub fn allocate_frame_cont(_size: usize) -&gt; Option&lt;usize&gt; {
    // TODO
    None
}

/// 释放给定地址的物理页帧
pub fn deallocate_frame(_frame: usize) {
    // TODO
}
<span class="boring">}</span></code></pre></pre>
<blockquote>
<p><em><strong>练习1</strong></em></p>
<p>管理<code>bootloader</code>给定的可用物理地址范围，实现物理页帧的分配和回收，完成后可设计测试用例验证分配器正确性。</p>
</blockquote>
<h3 id="物理页帧到虚拟页的映射"><a class="header" href="#物理页帧到虚拟页的映射">物理页帧到虚拟页的映射</a></h3>
<p>接下来我们将实现物理页帧到虚拟页的映射。首先在<code>kernel/src/mem/page_table.rs</code>中，实现<code>page_table.map(vaddr, paddr, flags)</code>函数功能：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 在kernel/src/mem/page_table.rs中

use x86_64::{instructions::tlb, structures::paging::PageTableFlags};

/// 主要实现页表映射相关功能
#[derive(Debug, Default)]
#[allow(dead_code)]
pub struct PageTable {
    /// 页表的基地址
    paddr: usize,
}

#[allow(dead_code)]
impl PageTable {
    /// 使用已有物理页帧作为基地址创建页表
    pub fn new(paddr: usize) -&gt; Self {
        PageTable { paddr }
    }

    /// 获取页表基地址
    pub fn paddr(&amp;self) -&gt; usize {
        self.paddr
    }

    /// 将paddr所在物理页帧映射至虚拟页page，并设置标记flags
    pub fn map(&amp;self, _vaddr: usize, _paddr: usize, _flags: PageTableFlags) {
        // TODO

        // 完成映射后刷新tlb
        tlb::flush_all();
    }
}
<span class="boring">}</span></code></pre></pre>
<p>在实现<code>map</code>函数的过程中，需要访问给定物理地址的内容，但我们内核运行于虚存空间中（<code>bootloader</code>为内核创建了地址空间，并加载映射内核），为访问物理页，<code>bootloader</code>将物理地址映射到以<code>0xFFFF_FF80_0000_0000</code>为偏移的虚拟地址，代码中的<code>phys_to_virt</code>函数可以帮助获取一个物理地址对应的虚拟地址，读写此虚拟地址等同于读写物理地址。</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// 在kernel/src/mem/mod.rs中
/// 物理地址偏移
pub const KERNEL_PHY_OFFSET: usize = 0xFFFF_FF80_0000_0000;

/// 物理地址转虚拟地址
pub fn phys_to_virt(paddr: usize) -&gt; usize {
    KERNEL_PHY_OFFSET + paddr
}
<span class="boring">}</span></code></pre></pre>
<p>接下俩，我们可以在<code>kernel/src/mem/mod.rs</code>中对内存管理初始化进行扩展，完成页帧到虚拟地址的映射：</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>mod page_table;

/// 内存页大小
pub const PAGE_SIZE: usize = 4096;

/// 堆内存页数量
pub const HEAP_PAGES: usize = 1024;

/// 堆内存基地至
pub const HEAP_BASE: usize = 0xFFFF_FF00_0000_0000;

/// 初始化内存管理
pub fn init&lt;'a&gt;(memory_regions: &amp;'a mut MemoryRegions) {
    // 1. 创建物理页帧分配器，并分配一段连续物理页帧作为内核堆内存
    [...]
    let heap_frame = allocate_frame_cont(HEAP_PAGES).expect(&quot;Failed to allocate frame&quot;);
    // 2. 将堆内存的每个页帧映射到相应虚拟地址
    let page_table = PageTable::new(kernel_base());
    let flags = PageTableFlags::PRESENT | PageTableFlags::WRITABLE;
    for i in 0..HEAP_PAGES {
        let vaddr = HEAP_BASE + i * PAGE_SIZE;
        let paddr = heap_frame + i * PAGE_SIZE;
        page_table.map(vaddr, paddr, flags);
    }
}

/// 获取内核态虚存基地址
pub fn kernel_base() -&gt; usize {
    Cr3::read().0.start_address().as_u64() as _
}
<span class="boring">}</span></code></pre></pre>
<blockquote>
<p><em><strong>练习2</strong></em></p>
<p>新分配一段连续的物理页，并映射到一段连续的虚存空间中。</p>
</blockquote>
<h3 id="实现堆内存分配器选做"><a class="header" href="#实现堆内存分配器选做">实现堆内存分配器（*选做）</a></h3>
<p>Rust中为使用堆内存需要一个实现了<code>GlobalAlloc trait</code>的堆内存分配器，在可以使用<code>std</code>标准库的场景下，标准库实现了堆内存分配器，我们就可以直接使用堆。但在内核开发中没有<code>std</code>库，需要自己实现堆内存分配器。</p>
<blockquote>
<p><em><strong>练习3</strong></em></p>
<p>将新映射的虚存空间作为内核的堆内存，以支持动态数据结构。</p>
<p>提示</p>
<ul>
<li>可以参照<a href="https://doc.rust-lang.org/std/alloc/index.html">官方文档</a>中的示例自己实现一个堆内存分配器，也可以直接使用社区中已有的第三方库<a href="https://crates.io/crates/buddy_system_allocator">buddy_system_allocator</a>实现堆内存分配器。之后需要取消kernel/src/lib.rs文件头部alloc相关代码的注释。</li>
<li>完成后，我们可以使用诸如Vec、String等使用堆内存的数据结构，可设计测试用例验证分配器正确性。</li>
</ul>
</blockquote>
<h3 id="命令解释器的重新实现选做"><a class="header" href="#命令解释器的重新实现选做">命令解释器的重新实现（*选做）</a></h3>
<p>大家在实验2中的命令解释器实现是如果使用了<code>String</code>类型，会因为没有实现Rust中的<code>GlobalAlloc trait</code>而报错，因此，在练习3的基础上，我们现在可以用更加简洁优美的方式重新实现命令解释器。</p>
<blockquote>
<p>*** 练习4***</p>
<p>请使用<code>String</code>类型重新实现命令解释器的相关功能。</p>
</blockquote>
<h2 id="小结"><a class="header" href="#小结">小结</a></h2>
<p>请在完成实验之后提交实验报告和所有源码，实验报告应记录实验过程和主要画面。</p>
<p>通过本实验，相信大家能够对内存管理有更加深入的理解。</p>
<h2 id="下一个实验"><a class="header" href="#下一个实验">下一个实验</a></h2>
<p>实现系统对协程与异步的支持。请提前学习Rust语言特性中与协程有关的相关内容并复习进程管理的相关知识点。</p>
<h2 id="参考资料"><a class="header" href="#参考资料">参考资料</a></h2>
<ol>
<li>Rust官方文档示例：<a href="https://doc.rust-lang.org/std/alloc/index.html">https://doc.rust-lang.org/std/alloc/index.html</a></li>
<li>buddy_system_allocator库：<a href="https://crates.io/crates/buddy_system_allocator">https://crates.io/crates/buddy_system_allocator</a></li>
</ol>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="lab_2.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="lab_4.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="lab_2.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="lab_4.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>

        <!-- Livereload script (if served using the cli tool) -->
        <script>
            const wsProtocol = location.protocol === 'https:' ? 'wss:' : 'ws:';
            const wsAddress = wsProtocol + "//" + location.host + "/" + "__livereload";
            const socket = new WebSocket(wsAddress);
            socket.onmessage = function (event) {
                if (event.data === "reload") {
                    socket.close();
                    location.reload();
                }
            };

            window.onbeforeunload = function() {
                socket.close();
            }
        </script>



        <script>
            window.playground_copyable = true;
        </script>


        <script src="elasticlunr.min.js"></script>
        <script src="mark.min.js"></script>
        <script src="searcher.js"></script>

        <script src="clipboard.min.js"></script>
        <script src="highlight.js"></script>
        <script src="book.js"></script>

        <!-- Custom JS scripts -->


    </div>
    </body>
</html>
